package com.gwcloud.leetcode.tags.dp;

/** 
* @ClassName   : Leetcode0213 
* @author      : ganwei 
* @date        : 2020年5月18日 
* @Description : 213 打家劫舍 II 
*/
public class Leetcode0213 {
    /**
     * -解题思路，动态规划
     */
	public int rob(int[] nums) {
		int n = nums.length;
		if(n==1) return nums[0];
		return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
	}
	
	public int robRange(int[] nums, int start, int end) {
		int d_i_1 = 0, d_i_2 = 0;
		int d_i = 0;
		for(int i = end; i >= start; i--) {
			d_i = Math.max(d_i_1, d_i_2 + nums[i]);
			d_i_2 = d_i_1;
			d_i_1 = d_i;
		}
		return d_i;
	}
    /**
     * -主函数
     */
    public static void main(String[] args) {
    	Leetcode0213 l0213 = new Leetcode0213();
    	int[] nums = {1,2,3,1};
    	System.out.println(l0213.rob(nums));
    }
}
